Data is often collected and stored in databases. Access to a database is managed by a database management system, such as a relational database management system (DBMS or RDBMS). To retrieve or update data in a database, database queries, such as Structured Query Language (SQL) queries, are submitted to the database management system.
A database typically includes multiple tables, where each table contains data arranged in rows and columns. In large databases, tables can be relatively large in size. To allow more efficient access of tables within the database, indices are typically maintained for the tables in the database. An index is a data structure that contains an arrangement of data values of one or more attributes (referred to as a key) which are arranged in some sorted order (e.g., ascending sorted order or descending sorted order). In response to a query to access a table on which an index is maintained, database software can access the index to quickly find the locations within the table that contain the requested data. There are various types of indices, including B-tree indices, hash indices, and others. B-tree indices are the most widely used in database management systems.
Building an index for large databases can be a relatively time-consuming process, especially for databases containing terabytes or other large amounts of data. As indices are being built, the tables that are involved are locked such that users do not have access to such locked tables. The relatively large amount of time that a database table may be unavailable for use during index building can reduce the performance of the database system.